// Singly Linked List.hpp
// Author: Paddy Huang
// Date: 2020.03.09 20:29

// Index from 0 internally, from 1 externally
#ifndef LINK_LIST_HXX
#define LINK_LIST_HXX

#include <iostream>
#include <stdlib.h>
using namespace std;

#define MAXSIZE 10000
#define ERROR -1

template<class T>
class Node{
	public:
		T data;
        Node<T> *next;
};

template<class T>
class LinkList{
	public:
		LinkList();  // Constructor
        ~LinkList(); // Destructor
        void CreateLinkList(int number);
        const void TraverseLinkList() noexcept;
        const bool isEmpty() noexcept;
        const bool isFull() noexcept;
        const int GetLength() noexcept;
        Node<T>* GetElemByElem(T data);
        Node<T>* GetElemByIndex(int index);
        void InsertLinkList(int index, T data);
        void InsertLinkListAtHead(T data);
        void InsertLinkListAtRear(T data);
        void DeleteElem(int index);
        void DeleteElemByElem(T data);
        void DeleteAll();
        void DeleteAtHead();
	private:
		Node<T> *head;
		int length;
};

template<class T>
LinkList<T>::LinkList(){
	head = new Node<T>();
    head->next = NULL;
	length = 0;
}

template<class T>
LinkList<T>::~LinkList(){
	head->next = NULL;
    delete head;
}

template<class T>
void LinkList<T>::CreateLinkList(int number){
	if(number < 0 || number > MAXSIZE){
		cout << "Invalid Size for List" << endl;
		exit(ERROR);
	}
	for(int i = 0; i < number; i++){
		cout << "Element No." << i + 1 << " : "; 
		Node<T> *node = (Node<T>*)malloc(sizeof(Node<T>));
        cin >> node->data;
        node->next = head->next;
        head->next = node;
	}
	length = number;
}

template<class T>
const void LinkList<T>::TraverseLinkList() noexcept {
	if(length == 0){
        cout << "Empty list." << endl; 
        return;
    }
    Node<T> *p = head->next;
    for(int i = 0; p != NULL; p = p->next, i++)
        cout << "Element No." << i + 1 << " : " << p->data << endl;
}

template<class T>
const bool LinkList<T>::isEmpty() noexcept {
    return length <= 0;
}

template<class T>
const bool LinkList<T>::isFull() noexcept {
    return length >= MAXSIZE;
}

template<class T>
const int LinkList<T>::GetLength() noexcept {
    return length;
}

template<class T>
Node<T>* LinkList<T>::GetElemByElem(T data){
	for(Node<T> *p = head->next; p != NULL; p = p->next)
        if(p->data == data)
            return p;
    return NULL;
}

template<class T>
Node<T>* LinkList<T>::GetElemByIndex(int index){
	if(index < 1 || index > length){
        cout << "Index not exists" << endl; 
        return NULL;
    }
	Node<T> *p = head;
    for(int i = 1; i <= index; p = p->next, i++);
    
    if(p) return p;
    return NULL;
}

template<class T>
void LinkList<T>::InsertLinkList(int index, T data){
	if(index < 1 || index > length) {
        cout << "Invalid index" << endl; return;
    }
	if(length >= MAXSIZE) {
        cout << "List is full" << endl; return;
    }

	Node<T> *pre = GetElemByIndex(index);
    Node<T> *node = (Node<T>*)malloc(sizeof(Node<T>));
    node->data = data;
    node->next = pre->next;
    pre->next = node;

	length++;
}

template<class T>
void LinkList<T>::InsertLinkListAtHead(T data){
	if(length >=  MAXSIZE) {
        cout << "List is full" << endl; 
        return;
    }
	
    Node<T> *node = (Node<T>*)malloc(sizeof(Node<T>));
    node->data = data;
    node->next = head->next;
    head->next = node;

	length++;
}

template<class T>
void LinkList<T>::InsertLinkListAtRear(T data){
	if(length >=  MAXSIZE) {cout << "List is full" << endl; return;}

	Node<T> *pre = length == 0 ? head : GetElemByIndex(length);
    Node<T> *node = (Node<T>*)malloc(sizeof(Node<T>));
    node->data = data;
    node->next = pre->next;
    pre->next = node;

	length++;
}    

template<class T>
void LinkList<T>::DeleteElem(int index){
	if(index < 1 || index > length) {cout << "Invalid index" << endl; return;}

	Node<T> *pre = GetElemByIndex(index - 1);
    Node<T> *p = pre->next;    // Current node to be deleted
    pre->next = p->next;

	length--;
}

template<class T>
void LinkList<T>::DeleteElemByElem(T data){
	int index = 1;
    Node<T> *p = head->next;
	while(p && p->data != data) {
        p = p->next; 
        index++;
    }
	if(p == NULL) {
        return;
    }
    Node<T> *pre = GetElemByIndex(index - 1);
    pre->next = p->next;
    
	length--;
}   

template<class T>
void LinkList<T>::DeleteAll(){
	head->next = NULL;
	length = 0;
}              

template<class T>
void LinkList<T>::DeleteAtHead(){
    head->next = head->next->next;
	length--;
}

#endif
